package com.mdnote.practice.dp;

/**
 * @author Rhythm-2019
 * @version 1.0
 * @date 2020/9/18
 * @description  不同路径 II (带障碍物)
 */
public class LeetCode63 {

    public static void main(String[] args) {
        LeetCode63 leetCode63 = new LeetCode63();

        int[][] board = {
                {0, 0, 0, 0, 0},
                {0, 0, 0, 0, 1},
                {0, 0, 0, 1, 0},
                {0, 0, 1, 0, 0},
//                {0, 0, 0},
//                {0, 1, 0},
//                {0, 0, 0}
        };
        int res = leetCode63.uniquePathsWithObstacles(board);
        System.out.println(res);
    }

    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        if (obstacleGrid[obstacleGrid.length - 1][obstacleGrid[0].length - 1] == 1) {
            return 0;
        }
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        // recursion
//        int count = recursion(0, 0, obstacleGrid);

        int count = dp(obstacleGrid);
        return count;

    }

    private int dp(int[][] board) {

        int row = board.length;
        int column = board[0].length;
        
        int[][] dp = new int[row][column];
        // 初始化最右边那一列
        dp[row - 1][column - 1] = 1;
        for (int i = row - 2; i >= 0; i--) {
            // 当前的地方不是障碍物而且下一步能走 避免{0, 0, 1, 0, 0}这种情况
            if (board[i][column - 1] != 1 && dp[i + 1][column - 1] != 0) {
                dp[i][column - 1] = 1;
            }
        }
        for (int i = column - 2; i >= 0; i--) {
            if (board[row - 1][i] != 1 && dp[row - 1][i + 1] != 0) {
                dp[row - 1][i] = 1;
            }
        }
        for (int i = row - 2; i >= 0; i--) {
            for (int j = column - 2; j >= 0; j--) {
                if (board[i][j] == 0) {
                    dp[i][j] = dp[i][j + 1] + dp[i + 1][j];
                }
            }
        }
        return dp[0][0];
    }



    private int recursion(int row, int column, int[][] obstacleGrid) {

        // Terminator
        // 边界
        if (row == obstacleGrid.length || column == obstacleGrid[0].length) {
            return 0;
        }
        // 结果
        if (row + 1 == obstacleGrid.length && column + 1 == obstacleGrid[0].length) {
            obstacleGrid[row][column] = 1;
            return 1;
        }
        // 障碍物
        if (obstacleGrid[row][column] == 1) {
            return 0;
        }
        // Process current logic
        if (obstacleGrid[row][column] == 0) {
            obstacleGrid[row][column] = recursion(row + 1, column, obstacleGrid) + recursion(row, column + 1, obstacleGrid);
        }
        return obstacleGrid[row][column];
    }
}
